import java.util.Stack;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: Admin
 * Date: 2022-05-12
 * Time: 21:04
 */
public class Main {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        if(pushA == null || popA == null) {
            return false;
        }
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int j = 0;

        for(i = 0; i < pushA.length; i++) {
            stack.push(pushA[i]);

            while(!stack.empty() && j < popA.length && stack.peek() == popA[j]) {
                stack.pop();
                j++;
            }
        }
        if(stack.empty()) {
            return true;
        } else {
            return false;
        }
    }
    private boolean isFull1(String str) {
        if (str.equals("+") || str.equals("-") || str.equals("*") || str.equals("/")) {
            return true;
        }
        return false;
    }

    public int evalRPN(String[] tokens) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < tokens.length; i++) {
            String x = tokens[i];

            if (!isFull1(x)) {
                stack.push(Integer.parseInt(x));
            } else {

                int num1 = stack.pop();
                int num2 = stack.pop();

                switch (x) {
                    case "+":
                        stack.push(num2 + num1);
                        break;

                    case "-":
                        stack.push(num2 - num1);
                        break;

                    case "*":
                        stack.push(num2 * num1);
                        break;

                    case "/":
                        stack.push(num2 / num1);
                        break;
                }

            }
        }
        return stack.pop();
    }


    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for(int i = 0; i < s.length();i++) {
            char ch = s.charAt(i);

            if(ch == '(' || ch == '[' || ch == '{') {
                stack.push(ch);
            } else {

                if(stack.empty()) {
                    return false;
                }
                char sh = stack.peek();

                if(sh == '(' && ch ==')' || sh =='[' && ch == ']' || sh== '{' && ch == '}') {
                    stack.pop();
                } else {
                    return false;
                }
            }
        }
        if(!(stack.empty())) {
            return false;
        }
        return true;
    }
    public boolean isValid1(String s) {

        Stack<Character> stack = new Stack<>();

        for(int i = 0; i< s.length();i++) {
            char ch = s.charAt(i);
            if(ch == '(' || ch == '[' || ch == '{') {
                //如果是左括号，就入栈
                stack.push(ch);
            }else{
                if(stack.empty()) {
                    //遇到右括号了，但是当前栈是空的
                    return false;
                }
                char c = stack.peek();
                if(c == '(' && ch == ')' || c == '[' && ch == ']' || c == '{' && ch == '}' ) {
                    stack.pop();//当前的这两个括号是匹配的
                }else{
                    //当前这两个括号 不匹配
                    return false;
                }
            }
        }

        if(!stack.empty()) {
            return false;//栈当中 还存在左括号！
        }

        return true;
    }
}
